Among the primary objectives of a digital data compression system are the removal of redundant information and the accurate representation of remaining information using a minimum number of bits, before the data is conveyed via a transmission channel or storage medium. Data to be compressed may represent various types of information, such as audio and video information for example.
Coding of data for compression often requires that two factors be considered in particular, namely, the location of significant data and the value of significant non-zero data. Compression coding of data locations, which may be represented by the entries of a so-called significance map, advantageously augments the coding of the significant non-zero data.
Recent developments in the field of image signal processing, among others, continue to focus attention on a need for efficient and accurate forms of data compression coding. In this regard various forms of so-called "pyramid" signal processing have been proposed, particularly in the context of image information processing. Multiresolution "pyramid" processing of image data is described, for example, by Burr et al. in "The Laplacian Pyramid as a Compact Image Code", IEEE Transactions on Communications, Vol. Com-31, No. 4, April 1983. A so-called "wavelet" pyramid is a specific type of multiresolution pyramid that uses quadrature mirror filters (QMF) to produce subband decompositions of an original image representative video signal. A signal processor of this type is described by Pentland et al. in "A Practical Approach to Fractal-Based Image Compression", Proceedings of the DCC '91 Data Compression Conference, Apr. 8-11, 1991, IEEE Computer Society Press, Los Alamitos, Calif. The Pentland et al. compression system attempts to use low frequency coarse scale information to predict significant information at high frequency finer scales. QMF subband pyramid processing also is described in the book "Subband Image Coding", J.W. Woods, ed., Kluwer Academic Publishers, 1991.
Another system for pyramid processing image data is described by Lewis et al. in "A 64 Kb/s Video Codec Using the 2-D Wavelet Transform", Proceedings of the DCC '91 Data Compression Conference as mentioned above. Lewis et al. describe a coding system based on a model of human visual perception. Decomposed high pass bands are coded by constructing spatially local trees having nodes comprising2.times.2 blocks of subtrees. The energy (a statistical measure) of a tree is compared with a human visual system weighted threshold to determine if a tree is important or not. If not, the coder assumes that the remainder of the tree if zero and a "zero flag" is sent.
A data compression system disclosed by J.M. Shapiro in a copending U.S. patent application Ser. No. 790,860 uses the absence of significant low frequency coarse scale information to predict the absence of significant information at higher frequency finer scales, in contrast to the Pentland et al. system which conversely attempts to predict significant information. In addition, the Shapiro system advantageously does not rely upon a statistical measure, such as energy, associated with a block of plural coefficients as in Lewis et al., since such reliance may lead to a significant coefficient being obscured by surrounding insignificant coefficients. Also unlike Lewis et al., the Shapiro system guarantees that for a given threshold neither a root element of a tree structure nor any descendant of a root element has a magnitude greater than the threshold.
It is herein recognized that a variant of the Shapiro system, as disclosed herein, can result in improved coding performance, albeit at the expense of an increase in memory and computation In the zerotree structure of the previously mentioned Shapiro system, a large significant coefficient value occurring at an intermediate (leaf) node in the tree structure would prevent the node ancestors from being a zerotree root in future evaluations at progressively smaller thresholds, e.g., in association with a successive approximation quantizer. In the system disclosed herein, using a successive approximation quantizer, once a coefficient is found to be significant, it is no longer necessary to include it in significance maps at smaller thresholds. Thus in accordance with the principles of the present invention, a significant coefficient found at an intermediate (e.g., leaf) node does not prevent an ancestor (at a coarser level) from being a zerotree root on future evaluations at smaller thresholds.